package com.leetcode.partition5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/11/10 8:55
 */
public class LC495提莫攻击 {

    public static int findPoisonedDuration(int[] timeSeries, int duration) {
        return stimulation(timeSeries, duration);
    }

    public static void main(String[] args) {
        int[] timeSeries = {1, 2, 3, 8, 15};
        int duration = 4;
//        int[] timeSeries = {1, 5};
//        int duration = 2;
        System.out.println(findPoisonedDuration(timeSeries, duration));
    }

    private static int stimulation(int[] timeSeries, int duration) {
        int answer = 0, lastEndTime = Integer.MIN_VALUE;
        for (int startTime : timeSeries) {
            int endTime = startTime + duration - 1;
            answer += lastEndTime < startTime ? duration : endTime - lastEndTime;
            lastEndTime = endTime;
        }
        return answer;
    }

    private static int greedyImprove(int[] timeSeries, int duration) {
        int answer = 0;
        for (int i = 0; i < timeSeries.length; i++) {
            //当前攻击能持续的时间区间
            int startTime = timeSeries[i], endTime = timeSeries[i] + duration;
            //找重叠时间区间
            while (i + 1 < timeSeries.length && timeSeries[i + 1] <= endTime) {
                endTime = Math.max(endTime, timeSeries[i + 1] + duration);
                i++;
            }
            answer += endTime - startTime;
        }
        return answer;
    }

    private static int greedy(int[] timeSeries, int duration) {
        int answer = 0;
        int[][] intervals = new int[timeSeries.length][2];
        for (int i = 0; i < timeSeries.length; i++) {
            intervals[i][0] = timeSeries[i];
            intervals[i][1] = timeSeries[i] + duration;
        }
        List<int[]> mergeIntervals = new ArrayList<>();
        //合并区间
        for (int i = 0; i < intervals.length; i++) {
            //得到当前攻击的持续时间，作为一个时间区间
            int startTime = intervals[i][0], endTime = intervals[i][1];
            //以当前时间区间的结束时间找重叠区间
            while (i + 1 < intervals.length && intervals[i + 1][0] <= endTime) {
                endTime = Math.max(endTime, intervals[i + 1][1]);
                i++;
            }
            mergeIntervals.add(new int[]{startTime, endTime});
        }
        //检查最后一个区间，如果最后一个区间没有被包括进去，需要添加最后一个区间
        if (mergeIntervals.get(mergeIntervals.size() - 1)[1] < intervals[intervals.length - 1][0]) {
            mergeIntervals.add(new int[]{intervals[intervals.length - 1][0], intervals[intervals.length - 1][1]});
        }
        mergeIntervals.forEach(val -> System.out.println(Arrays.toString(val)));
        //遍历所有合并后的区间，将中毒时间累加
        for (int[] mergeInterval : mergeIntervals) {
            answer += mergeInterval[1] - mergeInterval[0];
        }
        return answer;
    }
}
